// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8.
package info.iu9.interval_tree;
import java.util.*;



public class TreeIntervalSearchSet extends IntervalSearchSet {
  // Итератор, последовательно возращающих все числа из всех интервалов
  // в порядке возрастания.
  // @sa IntervalTree.Iterator.
  public class Iterator implements java.util.Iterator<Integer> {
    Iterator() {
      node_ = root_;
      if ( !node_.isNil() ) {
        moveLeft();
        value_ = node_.key().min() - 1;  // для первого next
      }
    }

    public void remove() { throw new UnsupportedOperationException(); }
    public boolean hasNext() {
      return !node_.isNil() &&
             node_.key().max() > value_ ||
             nodeHasRightChild() ||
             !stack_.empty();
    }
    public Integer next() {
      if ( !hasNext() ) { throw new NoSuchElementException(); }
      if ( node_.key().max() > value_ ) {
        return ++value_;
      }
      if ( nodeHasRightChild() ) {
        moveRight();
      } else if ( !stack_.empty() ) {
        moveUpTo(stack_.pop());
      }
      value_ = node_.key().min();
      return value_;
    }

    private void moveLeft() {
      while ( nodeHasLeftChild() ) {
        stack_.push(node_);
        node_ = node_.child(left);
      }
    }
    private void moveRight() {
      node_ = node_.child(right);
      moveLeft();
    }
    private void moveUpTo(final Node node) {
      while ( node_ != node ) {
        node_ = node_.parent();
      }
    }

    private boolean nodeHasLeftChild() {
      return !node_.child(left).isNil();
    }
    private boolean nodeHasRightChild() {
      return !node_.child(right).isNil();
    }

    static final boolean left = true;
    static final boolean right = !left;

    private final Stack<Node> stack_ = new Stack<Node>();
    // Индекс текущего узла.
    private Node node_;
    // Значение в узле.
    private int value_;
  }

  public TreeIntervalSearchSet clone() {
    try {
      final TreeIntervalSearchSet t = (TreeIntervalSearchSet)super.clone();
      t.root_ = root_.clone();
      return t;
    }
    catch(CloneNotSupportedException e) {
      assert false;
      return null;
    }
  }

  public Iterator iterator() {
    return new Iterator();
  }

  public boolean contains(final int value) {
    final boolean left = true;
    final boolean right = false;

    Node z = root_;
    while ( !z.isNil() && !isNodeContains(z, value) ) {
      final Node l = z.child(left);
      if ( !l.isNil() && l.additional() >= value ) {
        z = l;
      } else {
        z = z.child(right);
      }
    }
    return !z.isNil();
  }

  TreeIntervalSearchSet(final Node root) {
    root_ = root;
  }

  // Проверка условия наличия значения в заданном узле.
  private static boolean isNodeContains(final Node z, final int value) {
    assert !z.isNil();
    return z.key().min() <= value && value <= z.key().max();
  }

  private /*final*/ Node root_;
}
